package leetcode_1_200;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_120_3 {
    public static void main(String[] args) {
        List<List<Integer>> tes = new ArrayList<>();
        ArrayList<Integer> l1 = new ArrayList<>();
        l1.add(2);
        tes.add(l1);
        ArrayList<Integer> l2 = new ArrayList<>();
        l2.add(3);
        l2.add(4);
        tes.add(l2);
        ArrayList<Integer> l3 = new ArrayList<>();
        l3.add(6);
        l3.add(5);
        l3.add(7);
        tes.add(l3);
        ArrayList<Integer> l4 = new ArrayList<>();
        l4.add(4);
        l4.add(1);
        l4.add(8);
        l4.add(3);
        tes.add(l4);
        System.out.println(minimumTotal(tes));
    }
    private static int minimumTotal(List<List<Integer>> triangle) {
        int depth = triangle.size();
        List<List<Integer>> dp = new ArrayList<>();
        ArrayList<Integer> first = new ArrayList<>();
        first.add(triangle.get(0).get(0));
        dp.add(first);
        for (int i = 1; i < depth; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int j = 0; j < i + 1; j++) {
                if (j == 0) {
                    list.add(triangle.get(i).get(j) + dp.get(i - 1).get(j));
                    continue;
                }
                if (j == i) {
                    list.add(triangle.get(i).get(j) + dp.get(i - 1).get(j - 1));
                    continue;
                }
                list.add(triangle.get(i).get(j) + Math.min(dp.get(i - 1).get(j), dp.get(i - 1).get(j - 1)));
            }
            dp.add(list);
        }
        List<Integer> last = dp.get(depth - 1);
        int ans = Integer.MAX_VALUE;
        for (Integer num : last) {
            ans = Math.min(ans, num);
        }
        return ans;
    }
}
